package od_2025A.two;

import java.util.Scanner;
import java.util.Stack;

/**
 * http://blog.csdn.net/qq_45776114/article/details/146410574
 */
public class Test01 {

    static class Node {
        char value;
        Node left;
        Node right;

        Node(char val) {
            this.value = val;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 读取数据
        String treeStr = scanner.nextLine();
        // 关闭 scanner
        scanner.close();
        // 构建二叉树
        Node node = buildTree(treeStr);
        // 中序遍历二叉树
        in(node);
    }

    /**
     * treeStr示例：a{b{d,e{g,h{,i}}},c{f}}
     * 重点还是通过栈或者其他方式，模拟着将二叉树构建出来，
     * 就如同，我们借助栈进行先序，中序，后序遍历，考察的是对二叉树结构的熟悉，以及借助其他数据结构的能力
     * <p>
     * 整体思路，将二叉树所有节点压入栈中，然后当遇到 } 时，弹栈，组装二叉树
     * 具体在分析编写代码时，将字符串的结构拆道最小去考虑，其实就只有四种场景,将这四种场景归纳后，就可以得出规律；
     * 当遇到 { 时，记录当前的栈高，
     * 当遇到‘，’时，当前的栈高如果等于记录的栈高，则证明缺少左子节点，将左子节点补齐为 null
     * 当遇到 ‘}’时，当前的栈高 = 记录的栈高 + 1 ，证明缺少右子节点，补齐右子节点；
     * 这样就可以将这颗二叉树进行补全，然后在 遇见 ‘}’ 时，就可以弹栈，构建二叉树了
     * a {,}
     * a {b,}
     * a {,c}
     * a {b,c}
     * </p>
     *
     * @param treeStr
     * @return
     */
    private static Node buildTree(String treeStr) {
        // 1、树节点栈
        Stack<Node> stack = new Stack<>();
        // 2、记录的是每一个头节点时，栈中的高度
        Stack<Integer> stackSize = new Stack<>();
        Node root = null;
        // 轮询每个字符
        for (int i = 0; i < treeStr.length(); i++) {
            char cur = treeStr.charAt(i);
            if (cur == '{') {
                stackSize.push(stack.size());
            } else if (cur == ',') {
                // 补左子节点
                if (stack.size() == stackSize.peek()) {
                    stack.push(null);
                }
            } else if (cur == '}') {
                // 补右子节点
                if (stack.size() == stackSize.peek() + 1) {
                    stack.push(null);
                }
                Node right = stack.pop();
                Node left = stack.pop();
                Node peek = stack.peek();
                peek.left = left;
                peek.right = right;
                // 将最后记录的栈高度给pop出去，处理下一个头节点
                stackSize.pop();
            } else {
                Node curNode = new Node(cur);
                if (root == null) {
                    root = curNode;
                }
                stack.push(curNode);
            }
        }
        return root;
    }

    // 中序遍历
    private static void in(Node node) {
        if (node == null) {
            return;
        }
        in(node.left);
        System.out.print(node.value);
        in(node.right);
    }

}
